As is known in the art, interconnects between gates in Very Large Scale Integration (VLSI) chips cause propagation delays in the circuit. To approximate the actual delay, the interconnects are modeled with a circuit comprising resistors, inductors, and capacitors, i.e., an RLC interconnect model. For linear RLC circuits, the Asymptotic Waveform Evaluation (AWE) technique provides circuit response approximations. The transient portion of the response is approximated by matching the initial boundary conditions and the first 2q−1 moments of the exact response to a lower order q-pole model.
FIG. 1A illustrates an example model circuit. In the example model circuit 100, the capacitors have been replaced by current sources. (There were no inductors and thus no voltage sources.) The moments are represented by the voltages at each node of the circuit. To more easily represent these nodes, the example circuit 100 is represented by a parasitic graph. FIG. 1B illustrates the parasitic graph representation of the example model circuit. In the graph 102, each node is represented by a dot, each resistor is represented by an edge, and each current source is represented by an arrow.
The RLC interconnect model is first reduced and simplified. The delay and waveform at any point of the circuit are then determined by the poles and residues at that point. The poles and residues can be computed using the moments at the same point. Moments are computed by solving the DC solution of the circuit with capacitors replaced by current sources and inductors replaced by voltage sources.
However, in the ever-increasing complexity of circuits and the interconnects in VLSI design, there are hundreds or thousands or more nodes in the circuits. The conventional delay analysis using AWE is prohibitive for these cases. Also, the algorithm for the analysis has different approaches for different types of model circuits structures, and the amount of computation to obtain the moments are also not optimized.
Accordingly, there exists a need for an improved method for interconnect delay analysis for VLSI circuits. The improved method should be generalized for different types of model circuit structures and optimized to reduce the complexity of the computations. The present invention addresses such a need.